<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>Document</title>
</head>

<body>
    <script>
        let bubbleSort = (arr) => {
            let len = arr.length;
            for (let i = 0; i != len; i++) {
                for (let j = 0; j != len - i; j++) {
                    if (arr[j] > arr[j + 1]) {
                        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                    }
                }
            }
            return arr;
        }
        console.log("这是冒泡排序    begin");
        console.log(bubbleSort([8, 5, 7, 9, 42, 565, 123, 345, 56766]));
        console.log(bubbleSort([83, 5, 7, 9213, 42, 56, 13, 312345, 56766]));
        console.log("这是冒泡排序   end");
        // 冒泡排序的思想就是重复的走访要排序的数列，每次比较两个元素，如果顺序错误，那么就交换
        // 1. 比较项灵的元素，如果第一个比第二个打，那么久交换他们
        // 2. 对每一对相邻元素做同样的工作，从开始第一对到结束最后一对， 这样最后的元素都是最大的数。
        // 3. 针对所有元素重复上面的操作。除了最后一个
        // 4. 重复第一步到第三步
        // 平均时间复杂度是O（n2）
        // 最坏时间复杂度是O（n2）
        // 最好时间福大足是O（n） 当所有的数都有序的话，是不需要执行里面的交换的
        // 空间复杂度是O（1） 只需要一个temp
        // 是稳定排序

        let selectSort = arr => {
            let len = arr.length;
            let minIndex;
            for (let i = 0; i != len; i++) {
                minIndex = i;
                for (let j = i + 1; j != len; j++) {
                    if (arr[j] < arr[minIndex]) {
                        minIndex = j;
                    }
                }
                [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
            }
            return arr;
        }
        console.log("这是选择排序    begin");
        console.log(selectSort([8, 25, 7, 9, 42, 565, 123, 345, 56766]));
        console.log(selectSort([83, 5, 7, 9213, 42, 56, 13, 312345, 56766]));
        console.log("这是选择排序   end");
        // 选择排序的核心是在没有排序的队列中找到最小的元素，存放到排序队列的气势位置，最后，再继续寻找最小的元素放到已排序的末尾
        // 是表现的最为稳定的算法啊之一，无论什么数据都是O（n2）的时间复杂度，不需要占用额外的空间
        // 1. 初始状态都是无序区，有序区为空
        // 2. 找到最小的那个元素，与无序区第一个进行调换，那么以这个为中间，前面所有的都是有序的，后面的都是无序的，
        // 平均时间复杂度是O（n2）
        // 最坏时间复杂度是O（n2）
        // 最好时间复杂度是O（n2）
        // 空间复杂度是O（1） 因为需要temp来叫交换， 
        // 是不稳定排序

        let insertSort = arr => {
            let len = arr.length;
            let preIndex, current;
            for (let i = 1; i != len; i++) {
                preIndex = i - 1;
                current = arr[i];
                while (preIndex >= 0 && arr[preIndex] > current) {
                    arr[preIndex + 1] = arr[preIndex];
                    preIndex--;
                }
                arr[preIndex + 1] = current;
            }
            return arr;
        }
        console.log("这是插入排序    begin");
        console.log(insertSort([8, 25, 7, 9, 42, 565, 123, 345, 56766]));
        console.log(insertSort([83, 5, 7, 9213, 42, 56, 13, 312345, 56766]));
        console.log("这是插入排序   end");
        // 插入排序的核心是构建有序序列，对于没有排序的数据在已经排序的数据中从后向前扫描，找到相对应的位置插入。
        // 1. 从第一个元素开始，该元素可以默认是已经被排序
        // 2. 取出下一个元素，在已经排序的队列中从后向前扫描，如果这个元素大于新的元素，那么久移动位置
        // 3. 重复第二个步骤，直达找到找到已经排序的元素小于或者等于新元素的位置，把新元素插入到该位置之后
        // 4. 重复2-3操作
        // 平均时间复杂度是是O（n2）
        // 最差时间复杂度是是O（n2）
        // 最好时间复杂度是是O（n）
        // 空间复杂度是O（1） 
        // 稳定排序


        let shellSort = arr => {
            let len = arr.length;
            let gap = 1;
            while (gap < len / 3) {
                gap = gap * 3 + 1;
            }
            for (gap; gap > 0; gap = Math.floor(gap / 3)) {
                for (let i = gap; i != len; i++) {
                    temp = arr[i];
                    for (var j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
                        arr[j + gap] = arr[j];
                    }
                    arr[j + gap] = temp;
                }
            }
            return arr;
        }
        console.log("这是shell排序    begin");
        console.log(shellSort([84, 83, 88, 87, 61, 50, 70, 60, 88, 99]));
        console.log(shellSort([83, 5, 7, 9213, 42, 56, 13, 312345, 56766]));
        console.log("这是shell排序   end");
        // 希尔排序的核心是把待排序的记录序列分割成为若干个子序列分别进入直接插入排序
        // 1， 选择一个增量序列t1，t2，t3其中t1 最大tn最小
        // 2. 按照增量序列的个数n，对序列进行n次排序
        // 3. 每次排序根据对应的增量，吧代拍序列分割成若干长度为的子序列，分别对各子表进行直接插入排序，
        // 平均时间复杂度是O（n1.3）
        // 最坏时间复杂度是O（n2）
        // 最好时间复杂度是O（n）
        // 空间复杂度是O（1）
        // 是不稳定排序


        let mergeSort = arr => {
            let len = arr.length;
            if (len < 2) {
                return arr;
            }
            let middle = Math.floor(len / 2),
                left = arr.slice(0, middle),
                right = arr.slice(middle);
            return merge(mergeSort(left), mergeSort(right));
        }

        let merge = (left, right) => {
            let result = [];
            while (left.length > 0 && right.length > 0) {
                if (left[0] <= right[0]) {
                    result.push(left.shift());
                } else {
                    result.push(right.shift());
                }
            }
            while (left.length) {
                result.push(left.shift());
            }
            while (right.length) {
                result.push(right.shift());
            }
            return result;
        }

        console.log("这是归并排序    begin");
        console.log(mergeSort([84, 83, 88, 87, 61, 50, 70, 60, 88, 99]));
        console.log(mergeSort([83, 5, 7, 9213, 42, 56, 13, 312345, 56766]));
        console.log("这是归并排序   end");
        // 归并排序的核心是采用分治法，吧已经有序的子队列合并，得到完全有序的序列，也就是先让子序列有序。
        // 1. 吧长度为n的输入序列分成两个长度为n/2的子序列，对这个子序列再采用归并排序，
        // 合并成一个最终的序列
        // 平均时间复杂度为O（nlog2n）
        // 最好时间复杂度为O（nlog2n）
        // 最差时间复杂度为O（nlog2n）
        // 空间复杂度为O（n）
        // 是一个稳定的排序


        let quickSort = (arr, left, right) => {
            let len = arr.length,
                partitionIndex,
                left = typeof left != 'number' ? 0 : left,
                right = typeof right != 'number' ? len - 1 : right;
            if(left < right) {
                partitionIndex = partition(arr, left, right);
                quickSort(arr, left, partitionIndex - 1);
                quickSort(arr, partitionIndex + 1, right);
            }
            return arr;
        }
    </script>
</body>

</html>